package com.tgy.algorithm._经典题目01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _013_有序序列返回二元组和三元组 {


    public static ArrayList<int[]> findTwoNum(int[] nums,int k) {

        ArrayList<int[]> ints = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return ints;
        }

        return doFindTwoNum(nums,k,0,nums.length - 1);
    }

    public static ArrayList<int[]> doFindTwoNum(int[] nums,int k,int start, int end) {

        ArrayList<int[]> ints = new ArrayList<>();

        int left = start;
        int right = end;
        int sum = 0;
        while (left <= right) {

            sum = nums[left] + nums[right];
            if (sum < k) {
                left++;
            }else if (sum > k) {
                right--;
            }else {
                if (left > 0 && nums[left] == nums[left - 1]) {
                    left++;
                }else {
                    int[] ret = {nums[left], nums[right]};
                    ints.add(ret);
                    // 因为相等的时候是left++，所以下次判断是否是同一个相等使用 nums[left] == nums[left - 1]
                    left++;
                }
            }
        }

        return ints;
    }

    public static ArrayList<int[]> findThreeNum(int[] nums,int k) {

        ArrayList<int[]> ints = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return ints;
        }

        int len = nums.length;

        for (int i = 0; i < len - 2; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            ArrayList<int[]> twoNums = doFindTwoNum(nums, k - nums[i], i + 1, len - 1);
            if (!twoNums.isEmpty()) {
                for (int[] twoNum : twoNums) {
                    int[] ret = {nums[i], twoNum[0], twoNum[1]};
                    ints.add(ret);
                }
            }
        }

        return ints;
    }


    public static void main(String[] args) {
        // -2
        int[] nums = new int[]{-3,-3,-2,1,1,1,2,3,3,4};
//        ArrayList<int[]> twoNum = findTwoNum(nums, 1);
        ArrayList<int[]> twoNum = findThreeNum(nums, 0);
        for (int[] ints : twoNum) {
            System.out.println(Arrays.toString(ints));
        }

    }
}
